package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	dp := make([][2]int, len(prices)) // 0表示持有，1表示不持有
	dp[0][0] = -prices[0]
	dp[0][1] = 0
	for i := 1; i < len(prices); i++ {
		dp[i][0] = int(math.Max(float64(dp[i-1][0]), float64(0-prices[i])))          //持有的一定假设是i之前历史最低值
		dp[i][1] = int(math.Max(float64(dp[i-1][0]+prices[i]), float64(dp[i-1][1]))) //不持有的是当前值减去历史最低值 与 昨天手上总现金
	}
	return dp[len(prices)-1][1]
}

func maxProfit2(prices []int) int {
	min := prices[0]
	max := 0
	for i := 1; i < len(prices); i++ {
		if min > prices[i-1] {
			min = prices[i-1]
		}
		if prices[i]-min > max {
			max = prices[i] - min
		}
	}
	return max
}
